/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: lenovo
 * Date: 2022-08-31
 * Time: 16:05
 */
public class Sort {
    /*//main1
    public int[] elem;
    public int usedsize;

    public InsertSort(int[] elem, int usedsize) {
        this.elem = elem;
        this.usedsize = usedsize;
    }
    public void insertSort(){
        if(usedsize == 0){
            return;
        }
        for (int i = 1; i <usedsize ; i++) {
            int tmp = elem[i];
            int j = i-1;
            for (; j >=0 ; j--) {
                if(elem[j] >tmp){
                    elem[j+1] = elem[j];
                }else {
                    break;
                }
            }
            elem[j+1] = tmp;

        }

    }
    */

    /**
     * 插入排序
     * @param array
     */
    public static void insertSort0(int[] array){
        if(array.length == 0){
            return;
        }
        for (int i = 1; i < array.length; i++) {
            int tmp = array[i];
            int j = i-1;
            for (; j >=0; j--) {
                if(array[j]>tmp){
                    array[j+1] =array[j];
                }else {
                    break;
                }
            }
            //1.j<0,不满足循环条件,跳到这里,在下标0处方上最小的那个元素
            //2.i从前往后遍历,在j循环里遇到break跳出,此时,j处的元素小于tmp,将j+1处的值覆盖为tmp
            array[j+1] = tmp;

        }

    }

    public static void shell(int[] array,int gap){
        if(array.length==0)return;
        //这里i必须++
        for (int i = gap; i < array.length; i++) {//这里必须是i++,i+=gap,也能对是因为,最后一次选择排序gap==1,
            // 不管你上次分组排序是否正确,最后一次都能排序正确,但是时间复杂度提高
            int tmp = array[i];
            int j = i-gap;
            for (; j >=0 ; j-=gap) {
                if(array[j]>tmp){
                    array[j+gap] = array[j];
                }else {
                    break;
                }
            }
            array[j+gap] = tmp;
        }
    }

    /**
     * 希尔排序
     * @param array
     */
    public static void shellInset(int[] array){
        int gap = array.length;
        while (gap>1){
            shell(array,gap);
            gap=gap/2;
        }
        shell(array,1);
//        //增量一般不这么写
//        int[] drr = {5,2,1};
//        for (int i = 0; i < drr.length; i++) {
//            shell(array,drr[i]);
//
//        }
    }

    /**
     * 选择排序
     */
    public static void selectSort(int[] array){
        for (int i = 0; i < array.length; i++) {
            int minIndex = i;
            for (int j = i+1; j < array.length ; j++) {
                if(array[j] < minIndex){
                    minIndex = j;
                }

            }
            int tmp = array[i];
            array[i] = array[minIndex];
            array[minIndex]=tmp;
        }

    }
}
